package jjn.round2;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author Jiang Jining
 * @since 2023-05-19 22:16
 */
public class LeetCode1079_LetterTilePossibilities {
    public int numTilePossibilities(String tiles) {
        Map<Character, Integer> countMap = new HashMap<>();
        for (char c : tiles.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        return dfs(tiles.length(), countMap, countMap.keySet()) - 1;
    }
    
    private int dfs(int i, Map<Character, Integer> countMap, Set<Character> options) {
        if (i == 0) {
            return 1;
        }
        int total = 1;
        for (Character c : options) {
            if (countMap.get(c) > 0) {
                countMap.put(c, countMap.get(c) - 1);
                total += dfs(i - 1, countMap, options);
                countMap.put(c, countMap.get(c) + 1);
            }
        }
        return total;
    }
}
